import java.util.PriorityQueue;

/**
 * 295. 数据流的中位数
 * https://leetcode.cn/problems/find-median-from-data-stream/description/
 */
class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<>((a, b) -> b - a);//大根堆
        right = new PriorityQueue<>((a, b) -> a - b);//小根堆
    }

    public void addNum(int num) {
        int m = left.size(), n = right.size();

        if(m == n) {
            if(m == 0 || num <= left.peek()) left.offer(num);
            else {
                //num > left.peek()
                right.offer(num);
                left.offer(right.poll());
            }
        } else {//m == n+1
            if(num <= left.peek()) {
                left.offer(num);
                right.offer(left.poll());
            } else{
                //num > left.peek()
                right.offer(num);
            }
        }

    }

    public double findMedian() {
        return left.size() == right.size() ? (left.peek() + right.peek()) / 2.0 : left.peek();
    }
}